/**
 * 从第0级台阶上到第N级，每次只能向上1或2或3
 * 走一步到第j级的花费为
 *  Cost[j] + (1或2或3)的平方
 * Cost是已知数组
 * 从上楼的最小代价
 * 
 * D[i] = min(D[i-c] + Cost[i] + c^2, c=1,2,3)
 */
class Solution {
public:
    int climbStairs(int n, vector<int>& costs) {
        costs.insert(costs.begin(), 0);
        vector<int> D(n + 1, INT_MAX);
        D[0] = 0;
        
        for(int i=1;i<=n;++i){
            if(i >= 3){
                D[i] = min(D[i], D[i - 3] + 9 + costs[i]);
            }
            if(i >= 2){
                D[i] = min(D[i], D[i - 2] + 4 + costs[i]);
            }
            D[i] = min(D[i], D[i - 1] + 1 + costs[i]);
        }
        return D[n];
    }
};